矩阵中的路径

Posted on | | reads times

矩阵中的路径

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bccced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

  • 每次都根据一个点，从该点开始遍历是否已遍历的点是否符合被包含字符串，如果不包含则返回上一步并标记该点不符合要求，若回溯到第一点后不符合，则继续从下一点开始。该过程可用递归表示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function hasPath(matrix, rows, cols, path)
{
    // write code here
    const pathLength=0;
    const visited=new Array(rows*cols);
    for(var row=0;row<rows;row++){
        for(var col=0;col<cols;col++){
            if( findPath(matrix,rows,cols,row,col,pathLength,visited,path)){
                return true
            }
        }
    }
    return false;
}
function findPath(matrix,rows,cols,row,col,pathLength,visited,path){
    let haspath=false;
    if(path.length===pathLength)return true;
    if(row<rows&&
      col<cols&&
      row>=0&&
      col>=0&&
     ( matrix[row*cols+col]===path[pathLength])&&
       !visited[row*cols+col]){
        pathLength++;
        visited[row*cols+col]=true
        haspath=
        findPath(matrix,rows,cols,row+1,col,pathLength,visited,path)||
        findPath(matrix,rows,cols,row-1,col,pathLength,visited,path)||
        findPath(matrix,rows,cols,row,col+1,pathLength,visited,path)||
        findPath(matrix,rows,cols,row,col-1,pathLength,visited,path)
        if(!haspath){
            pathLength--;
            visited[row*cols+col]=false;
            }
    }
     return haspath
}